from typing import List

"""
执行用时 :
52 ms
, 在所有 Python3 提交中击败了
88.09%
的用户
内存消耗 :
15.2 MB
, 在所有 Python3 提交中击败了
12.50%
的用户
"""
class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return 0
        res = 0
        i = 0
        while i < n:
            if i + nums[i] >= n - 1:
                return res + 1
            max_value = i + nums[i]
            max_index = i
            for j in range(i + 1, max_value + 1):
                tmp = j + nums[j]
                if tmp > max_value:
                    max_value = tmp
                    max_index = j
                    print(j, max_value)
            else:
                res += 1  # 这一轮没找到肯定是要+1的
            i = max_index


def test():
    assert 2 == Solution().jump([2, 3, 1, 1, 4])


def test1():
    assert 0 == Solution().jump([1])


def test2():
    assert 2 == Solution().jump([7, 0, 9, 6, 9, 6, 1, 7, 9, 0, 1, 2, 9, 0, 3])

